package exam;

import java.util.HashMap;
import java.util.Map;

public class test7 {
    public static void main(String[] args) {

    }

    public int minNumberOfFrogs(String croakOfFrogs) {
        char[]ch=croakOfFrogs.toCharArray();
        Map<Character,Integer>map=new HashMap<>();
        for(int i=0;i<ch.length;i++){
            if(ch[i]=='c'){
                if(map.getOrDefault('k',0)!=0){
                    map.put('k',map.get('k')-1);
                }
                map.put('c',map.getOrDefault('c',0)+1);
            }else if(ch[i]=='r'){
                if(map.getOrDefault('c',0)==0){
                    return -1;
                }
                map.put('c',map.get('c')-1);
                map.put('r',map.getOrDefault('r',0)+1);
            }else if(ch[i]=='o'){
                if(map.getOrDefault('r',0)==0){
                    return -1;
                }
                map.put('r',map.getOrDefault('r',0)-1);
                map.put('o',map.getOrDefault('o',0)+1);
            }else if(ch[i]=='a'){
                if(map.getOrDefault('o',0)==0){
                    return -1;
                }
                map.put('o',map.get('o')-1);
                map.put('a',map.getOrDefault('a',0)+1);
            }else if(ch[i]=='k'){
                if(map.getOrDefault('a',0)==0){
                    return -1;
                }
                map.put('a',map.get('a')-1);
                map.put('k',map.getOrDefault('k',0)+1);
            }
        }
        if(map.get('c')!=0||map.get('r')!=0||map.get('o')!=0||map.get('a')!=0){
            return -1;
        }
        return map.get('k');
    }


    public String countAndSay(int n) {
        String ret="1";

        for(int i=1;i<n;i++){
            StringBuilder tmp=new StringBuilder();
            int len=ret.length();
            for(int left=0,right=0;right<len;){
                while(right<len&&ret.charAt(left)==ret.charAt(right)){
                    right++;
                }
                tmp.append(Integer.toString(right-left));
                tmp.append(ret.charAt(left));
                left=right;
            }
            ret=tmp.toString();
        }
        return ret;
    }

    public String convert(String s, int numRows) {
        if(numRows==1)return s;
        int d=numRows*2-2;
        StringBuilder ret=new StringBuilder();
        int len=s.length();
        for(int i=0;i<len;i+=d){
            ret.append(s.charAt(i));
        }

        for(int i=1;i<numRows-1;i++){
            for(int k=i,j=d-k;k<len||j<len;k+=d,j+=d){
                if(k<len)ret.append(s.charAt(k));
                if(j<len)ret.append(s.charAt(j));
            }
        }
        for(int i=numRows-1;i<len;i+=d){
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }

    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int time=0;
        for(int i=0;i<timeSeries.length-1;i++){
            if(timeSeries[i]+duration<timeSeries[i+1]){
                time+=duration;
            }else{
                time+=timeSeries[i+1]-timeSeries[i];
            }
        }
        time+=duration;
        return time;
    }


    public String modifyString(String s) {
        char[]ch=s.toCharArray();
        int n=s.length();
        for(int i=0;i<n;i++){
            if(ch[i]=='?'){
                for(char c='a';c<='z';c++){
                    if((i==0||c!=ch[i-1])&&(i==n-1||c!=ch[i+1])){
                        ch[i]=c;
                        break;
                    }
                }
            }
        }
        return String.valueOf(ch);
    }

    public int[] missingTwo(int[] nums) {
        int t=0;
        for(int i=1;i<=nums.length+2;i++)t^=i;
        for(int x:nums)t^=x;

        int i=0;
        while(true){
            if(((t>>i)&1)==1)break;
            i++;
        }
        int []ret=new int[2];
        for(int j=0;j<nums.length;j++){
            if(((nums[j]>>i)&1)==1){
                ret[0]^=nums[j];
            }else{
                ret[1]^=nums[j];
            }
        }
        for(int j=1;j<=nums.length+2;j++){
            if(((j>>i)&1)==1){
                ret[0]^=j;
            }else{
                ret[1]^=j;
            }
        }
        return ret;
    }


    public int singleNumber2(int[] nums) {
        int ret=0;
        for(int i=0;i<32;i++){
            int sum=0;
            for(int x:nums)
                if(((x>>i)&1)==1)
                    sum++;
            sum%=3;
            if(sum==1)
                ret|=1<<i;
        }
        return ret;
    }

    public int getSum(int a, int b) {
        while(b!=0){
            int x=a^b;
            b=(a&b)<<1;
            a=x;
        }
        return a;
    }



    public int missingNumber2(int[] nums) {
        int ret=0;
        for(int i=0;i<nums.length;i++){
            ret^=nums[i];
            ret^=i;
        }
        return ret^nums.length;
    }



    public int missingNumber(int[] nums) {
        int n=nums.length;
        int sum1=0;
        for(int i=0;i<nums.length;i++){
            sum1+=nums[i];
        }
        int sum2=n+(n*n-n)/2;
        return sum2-sum1;

    }


    public boolean isUnique(String astr) {
        if(astr.length()>26){
            return false;
        }
        int []bit=new int[26];
        for(int i=0;i<astr.length();i++){
            if(bit[astr.charAt(i)-'a']==1){
                return false;
            }else{
                bit[astr.charAt(i)-'a']=1;
            }
        }
        return true;
    }

    public int[] singleNumber3(int[] nums) {
        int []ret=new int[2];
        int t=0;
        for(int i=0;i<nums.length;i++){
            t^=nums[i];
        }
        int i=0;
        for(;i<32;i++){
            if(((t>>i)&1)==1){
                break;
            }
        }
        for(int j=0;j<nums.length;j++){
            if(((nums[j]>>i)&1)==1){
                ret[0]^=nums[j];
            }else{
                ret[1]^=nums[j];
            }
        }
        return ret;
    }

    public int singleNumber(int[] nums) {
        int t=0;
        for(int i=0;i<nums.length;i++){
            t^=nums[i];
        }
        return t;
    }


    public int[] countBits(int n) {
        int []ans=new int[n+1];
        for(int i=0;i<=n;i++){
            int count=0;
            for(int j=0;j<32;j++){
                if(((i>>j)&1)==1)count++;
            }
            ans[i]=count;
        }
        return ans;
    }

    public int hammingDistance(int x, int y) {
        int t=x^y;
        int len=0;
        for(int i=0;i<32;i++){
            if(((t>>i)&1)==1)len++;
        }
        return len;
    }


    public int hammingWeight(int n) {
        int count=0;
        for(int i=0;i<32;i++){
            if(((n>>i)&1)==1)count++;
        }
        return count;
    }
}
